Description大于1的正整数n可以分解为：n=x1 * x2 * … * xm。 例如，当n=12 时，共有8 种不同的分解式： 12=12； 12=6 * 2； 12=4 * 3； 12=3 * 4； 12=3 * 2 * 2； 12=2 * 6； 12=2 * 3 * 2； 12=2 * 2 * 3。 对于给定的正整数n，计算n共有多少种不同的分解式。

Input输入数据只有一行，有1个正整数n (1≤n≤2000000000)。

Output将计算出的不同的分解式数输出。

Sample Input121Sample Output81递归分治法:耗时有些大，但是通过了。

f ( n ) f(n)f(n) 为n的不同分解式个数。

f ( n ) = ∑ n % i = = 0 f ( n / i ) , 2 < = i < = n f(n) = \sum_{n\%i==0} f(n/i),\\ 2 =1​

// 动态规划#include #include

using namespace std;

int solve(int n){ // factor数组存因子, dp数组存分解式个数, cnt记录因子个数 int factor[2000], dp[2000], cnt = 0, i; // 找出n的因子 for (i = 1; i * i < n; i++) // 循环次数缩减到sqrt(n) { if (n % i == 0) { factor[cnt++] = i; // i为因子 factor[cnt++] = n / i; // n/i也为因子 } } if (i * i == n) factor[cnt++] = i; // 如果i*i==n, i也为因子

sort(factor, factor + cnt); // 把因子从小到大排序 fill(dp, dp + cnt, 0); // 把dp数组初始化为0, 初始因子分解式个数都为0

dp[0] = 1; // 第一个因子(1)自己的分解式只有一个 for (i = 1; i < cnt; i++) // 从第二个因子开始, 循环找第i个因子的因子是否为前i-1个因子 for (int j = 0; j < i; j++) if (factor[i] % factor[j] == 0) // 如果第i个因子的因子是前i-1个因子中的, 第i个的分解式个数加上满足条件的 dp[i] += dp[j];

return dp[cnt - 1]; // dp[0]从0开始, cnt要减1}

int main(){ ios::sync_with_stdio(false); // 防止TLE cin.tie(NULL); cout.tie(NULL);

int n; cin >> n; cout